package com.lei.dynamic;

/**
 * @author: leiGer
 * @Date: 2021/12/15
 * @Time: 23:00
 */
public class climbStairs {
    /*
     * 1、动态规划
     * 到达第i个台阶所依赖的条件是来到它的前1个和前2个台阶所有的方法之和
     * 即：dp[i] = dp[i-1] + dp[i-2]
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public static int climbStairs(int n){
        if(n == 1){
            return 1;
        }
        int dp[] = new int [n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3;i<=n;i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
    /*
     * 2、斐波那契数
     * 其实爬楼梯的本质就是斐波那契数列：1、1、2、3、5、8、13......
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public static int Fibonacci(int n){
        if(n == 1){
            return 1;
        }
        int first = 1;//斐波那契数列第二个数
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
    public static void main(String[] args) {
        System.out.println(climbStairs(6));
        //System.out.println(Fibonacci(4));
    }
}
